// 数列0和1开始，后面每一项是前两项的和
// 思路1，动态规划
function fib(n) {
    let dp = []
    dp[0] = 0
    dp[1] = 1
    for (let i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2]
    }
    return dp[n]
}

console.log(fib(5))

// 思路2，动态规划简化版
function fib2(n) {
    if (n < 2) {
        return n
    }
    let res
    let pre = 0
    let cur = 1
    for (let i = 2; i <= n; i++) {
        res = pre + cur
        pre = cur
        cur = res
    }
    return res
}

console.log(fib2(5))

// 思路3，递归
function fib3(n) {
    function dfs(n) {
        if (n < 2) {
            return n
        }
        return dfs(n - 1) + dfs(n - 2)
    }
    return dfs(n)
}

console.log(fib3(5))